import java.util.ArrayList;
import java.util.List;

public class App {
    public static class Node{
        private int i;
        private int j;
        Node(int i,int j){
            this.i=i;
            this.j=j;
        }
        @Override
        public String toString() {
            return "("+this.i+","+this.j+")"+"->";
        }
    }
    public static void main(String[] args) throws Exception {
        //System.out.println(countWays(2, 2, 2));
        //System.out.println(f(10));
        int[][] maze=new int[8][7];
        for(int i=0;i<8;i++){
            maze[i][0]=1;
            maze[i][6]=1;
        }
        for(int i=0;i<7;i++){
            maze[0][i]=1;
            maze[7][i]=1;
        }
        maze[3][1]=1;
        maze[3][2]=1;
        for(int i=0;i<8;i++){
            for(int j=0;j<7;j++){
                System.out.print(maze[i][j]+" ");
            }
            System.out.println("");
        }
        
        List<Node> list=new ArrayList<Node>();

        findWay(maze, 1, 1,list);
        System.out.println("");
        System.out.println("");
        for(int i=0;i<8;i++){
            for(int j=0;j<7;j++){
                System.out.print(maze[i][j]+" ");
            }
            System.out.println("");
        }
        for(Node node:list){
            System.out.print(node);
        }
    }

    public static boolean findWay(int[][] maze,int i,int j,List<Node> list){
        if(maze[6][5]==2){//2为能走通
            return true;
        }else{
            if(maze[i][j]==0){
                maze[i][j]=2;//先假设能走通
                list.add(new Node(i, j));
                //按走下、右、上、左的顺序验证这个假设
                if(findWay(maze, i+1, j,list)){//下通
                    return true;
                }else if(findWay(maze, i, j+1,list)){//右通
                    return true;
                }else if(findWay(maze, i-1, j,list)){//上通
                    return true;
                }else if(findWay(maze, i, j-1,list)){//左通
                    return true;
                }else{
                    maze[i][j]=3;//全都走不通，说明这点就不可能到达终点，用3表示不可能到达终点的点
                    list.remove(list.size()-1);
                    return false;
                }
            }else{
                return false;
            }
        }
    }

    public static int countWays(int baskets,int capacity,int balls){
        if(baskets*capacity<balls||balls<=0){
            return 0;
        }
        if(baskets==1){
            return 1;
        }
        if(balls==1){
            return baskets;
        }
        if(capacity>balls){
            capacity=balls;
        }
        int count=baskets;
        for(int i=1;i<=capacity;i++){
            count+=countWays(baskets-1, capacity, balls-i);
        }
        return count;
    }
    public static int f(int n){
        int[] dp=new int[n];
        dp[0]=1;
        dp[1]=2;
        int i=2;
        while(i<n){
            dp[i]=dp[i-1]+dp[i-2];
            i++;
        }
        return dp[i-1];
    }
}
